package org.leetcode.middle.leetcode33;

import java.util.Arrays;

public class Solution
{

    public static void main(String[] args) {
        int []nums = {3,1};
        int index = search3(nums, 1);
        System.out.println(index);
    }

    public static int search3(int[] nums, int target) {
        int left = 0;
        int right =nums.length-1;
        while (left<=right){
            int mid =(left+right)>>>1;
            if (nums[mid]==target){
                return mid;
            }

            //前半段有序
            if (nums[mid]>=nums[left]){
                if (nums[left]<=target && target<nums[mid]){
                    right=mid-1;
                }else {
                    left=mid+1;
                }
            }else {
                if (nums[mid]<target && target<=nums[right]){
                    left=mid+1;
                }else {
                    right=mid-1;
                }
            }

        }

        return -1;
    }

    public  int search2 (int [] nums ,int target){

        int n = nums.length;

        if (n==1){
            return nums[0]==target ? 0:-1;
        }
        int left = 0;
        int right =nums.length-1;

        while (left<=right){
            int mid = (left+right)>>>1;
            if (nums[mid]==target){
                return mid;
            }

            //前半部分有序
            if (nums[left]<=nums[mid]){
                if (nums[left]<=target && target<=nums[mid]){
                    //目标值在前半截
                    right=mid-1;
                }else {
                    left=mid+1;
                }
            }else {
                //后半部分有序
                if (nums[mid]<=target && target<=nums[right]){
                    //目标值在后半截
                    left=mid+1;
                }else {
                    right=mid-1;
                }
            }
        }
        return -1;
    }
    public static int search (int [] nums ,int target)
    {
        int length = nums.length;
       int left =0,right =length-1;

       if (length==0)
       {
           return -1;
       }

       if (length==1)
       {
           return target==nums[0]?0:-1;
       }


       while (left<=right)
       {
           int mid = (left+right)>>>1;

           if (nums[mid]==target) {
               return mid ;
           }

           //前半截有序
           if (nums[0]<=nums[mid]) {
               //目标值在有序的前半截
               if (nums[0]<=target && target<nums[mid])
               {
                   right=mid-1;
               }else {
                   left=mid+1;
               }
           }else {
               //后半截有序
               if (nums[mid]<target && target<=nums[length-1])
               {
                   left=mid+1;
               }else {
                   right=mid-1;
               }

           }


       }
        return -1;
    }


}
